package cn.jm.study;

public class Quicksort {
	public final static int LENGTH = 10;

	public static void main(String[] args) {
		Quicksort home = new Quicksort();
		int[] arr;
		arr = home.init();
		

		home.show(arr);
		System.out.println("zaasas");
		home.quickSort(arr, 0, LENGTH - 1);
		home.show(arr);
	}

	private int[] init() {
		int[] arr = new int[LENGTH];
		int i = 0;
		for (; i < LENGTH; i++) {
			arr[i] = (int) (Math.random() * 1000000 % 900) + 100;
		}
		return arr;
	}

	private void show(int[] arr) {
		int i = 0;
		for (; i < LENGTH; i++) {
			System.out.printf("%8d",arr[i]);
		}
		System.out.println("\n-----------\n");
	}
	private void quickSort(int[] arr, int low, int high) {
		int pivotpos;
		if (low < high) {
			pivotpos = partition(arr, low, high);
			quickSort(arr, low, pivotpos - 1);
			quickSort(arr, pivotpos + 1, high);
		}
	}

	private int partition(int arr[], int low, int high) {
		int midvalue = arr[low];
		while (low < high) {
			while (low < high && arr[high] >= midvalue)
				high--;
			if (low < high)
				arr[low--] = arr[high];
			while (low < high && arr[low] <= midvalue)
				low++;
			if (low < high)
				arr[high--] = arr[low];
			
		}
		arr[low] = midvalue;
		return low;
	}
}